The present invention relates generally to forward error correction systems, and in particular to a product code based forward error correction system.
Digital electronic systems store and transmit copious amounts of information. Storage or transmission of digital information sometimes results, however, in corruption of some of the data. Defects in a storage media, or errors in the reading and writing of data from a storage media, may result in data errors. Similarly, transmission of data through a transmission channel may result in errors, through noise in the transmission channel or the inability of the transmitting or receiving unit to properly transmit or read data. As data storage and data transmission may be viewed as transmitting data to a media using a transmitting unit, and thereafter reading the data using a receiving unit, the remaining discussion will be in terms generally of data transmission.
Forward error correction (FEC) is often used to increase data reliability. Generally speaking, FEC systems encode data using an encoder at a transmitter and decode data using a decoder at the receiver. During encoding redundant information is added to the data. The redundant information allows determination by receiving units as to whether data corruption has occurred, and if so, the data that has been corrupted. Thus, the redundant information allows the data to be corrected within limits. The decoder generally decodes the data, generates an error polynomial, and uses the error polynomial to determine corrections to the data.
The encoded data is generally grouped in terms of code words. A code word is comprised of n symbols, of which k symbols are information symbols. The codeword therefore contains nxe2x88x92k redundant symbols. The symbols are data words comprised of m bits. In a systematic encoding system, the nxe2x88x92k redundant symbols are appended to the information symbols, while in a non-systematic code the information symbols are also modified. For instance, for BCH codes, n=2mxe2x88x921 and k=nxe2x88x92mt. To correct t bits within the code word, mt bits of overhead/redundancy is needed. Each of the k and n symbols is made of 1 bit. For Reed-Solomon (RS) codes, n=2mxe2x88x921 and k=nxe2x88x922t. For RS codes, to correct t symbols within the code word, 2t symbols of redundancy is needed. Each of the k and n symbols comprise m bits.
In order to increase data transmission reliability increased numbers of redundant symbols are required. The use of additional redundant symbols, however, decreases the effective bandwidth of a transmission system or reduces the total amount of storage space available in a storage system. Moreover, the use of additional redundant symbols increases the amount of processing performed by both the transmitting unit and the receiving unit to create or interpret the redundant symbols.
Moreover, different coding schemes have different abilities to correct different types of errors. For example, errors may be randomly distributed in a data set, or the errors may be grouped together, i.e. be burst errors. Generally speaking, increasing the number of bits within a symbol increases the ability of an FEC system to correct burst errors. However, as indicated above, increasing the number of bits per symbol also increases encoding and decoding circuit size and power requirements since the code word becomes longer.
The present invention provides a multi-dimensional forward error correction system. In one embodiment of the present invention comprises a method of performing a multi-dimensional forward error correction. The method includes encoding information symbols comprised of input data to form first code words and second code words, the first and second code words sharing at least some symbols. The method further comprises providing receipt symbols comprising potentially corrupted symbols of the first code words and second code words to a decoder. Potentially corrupted symbols are corrected by decoding the first received symbols, and further corrected by decoding the second received symbols, the second received symbols including symbols corrected during decoding of the first received symbols.
In a further embodiment, the received symbols are placed in a memory to form a multi-dimensional matrix, a first dimension of the multi-dimensional matrix being comprised of the first received symbols and the second dimension of the multi-dimensional matrix being comprised of the second received symbols. In a further embodiment the memory is comprised of virtual rows of symbols and virtual columns of symbols, and further includes placing corrected symbols in the memory in place of corrupted received symbols.
These and other aspects of the present invention are more readily understood when considered in conjunction with the accompanying drawings and the following detailed description.